#include <bits/stdc++.h>

using namespace std;

class Solution
{
public:
    // int trap(vector<int> &height)
    // {
    //     int length = height.size();
    //     int sum=0;
    //     for(int i=0;i<length;i++)
    //     {
    //         if(i==0||i==length-1)
    //         {
    //             continue;
    //         }
    //         int left_height=height[i];
    //         int right_height=height[i];
    //         for(int j=0;j<i;j++)
    //         {
    //             if(height[j]>left_height)
    //             {
    //                 left_height=height[j];
    //             }
    //         }
    //         for(int j=i+1;j<length;j++)
    //         {
    //             if(height[j]>right_height)
    //             {
    //                 right_height=height[j];
    //             }
    //         }
    //         int rain_height=min(left_height,right_height)-height[i];
    //         if(rain_height>0)
    //         {
    //             sum+=rain_height;
    //         }
    //     }
    //     return sum;
    // }

    // int trap(vector<int> &height)
    // {
    //     int size=height.size();
    //     vector<int> max_left_height(size,0);
    //     vector<int> max_right_height(size,0);
    //     max_left_height[0]=height[0];
    //     for(int i=1;i<size;i++)
    //     {
    //         max_left_height[i]=max(height[i],max_left_height[i-1]);
    //     }
    //     max_right_height[size-1]=height[size-1];
    //     for(int i=size-2;i>=0;i--)
    //     {
    //         max_right_height[i]=max(height[i],max_right_height[i+1]);
    //     }
    //     int sum=0;
    //     for(int i=1;i<size-1;i++)
    //     {
    //         int count=min(max_left_height[i],max_right_height[i])-height[i];
    //         if(count>0)
    //         {
    //             sum+=count;
    //         }
    //     }
    //     return sum;
    // }

    int trap(vector<int> &height)
    {
        stack<int> stk;
        int size = height.size();
        stk.push(0);
        int sum = 0;
        for (int i = 1; i < size; i++)
        {
            if (height[i] < height[stk.top()])
            {
                stk.push(i);
            }
            else if (height[i] == height[stk.top()])
            {
                stk.pop();
                stk.push(i);
            }
            else
            {
                while (!stk.empty() && height[i] > height[stk.top()])
                {
                    int mid = stk.top();
                    stk.pop();
                    if (!stk.empty())
                    {
                        int h = min(height[i], height[stk.top()]) - height[mid];
                        int w = i - stk.top() - 1;
                        sum += h * w;
                    }
                }
                stk.push(i);
            }
        }
        return sum;
    }
};

int main()
{
    vector<int> height{4, 2, 0, 3, 2, 5};
    Solution sol;
    cout << sol.trap(height) << endl;
    return 0;
}